# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/7 14:41 
"""

"""
判断有效的括号

"""


def valid_parenttheses(a):
    """
    判断当前输入的字符串中的括号是否有效
    """
    if a == '':
        return True
    left = ['(', '[', '{']
    right = [')', "]", "}"]
    right_left = {i: j for i, j in zip(right, left)}
    # 空栈
    tmp = []
    for i in a:
        if i in left:
            tmp.append(i)
        else:
            if len(tmp) == 0:
                return False
            else:
                if right_left[i] not in tmp:
                    return False
                else:
                    if right_left[i] != tmp[-1]:
                        return False
                    else:
                        tmp.pop(-1)
    if len(tmp) == 0:
        return True
    else:
        return False


"""

给定n代表生成括号的对数，请你写一个函数，使其能够生成所有可能的并且有效的括号组合
"""


def generate_parantheses(n):
    """
    判断生成的有效括号数
    """
    from itertools import permutations
    base = '()'
    new = list(base * n)
    all_likely = permutations(new, len(new))
    output = []
    for i in all_likely:
        tmp = []  # 空栈
        for j in i:
            if j == '(':
                tmp.append(j)
            else:
                if len(tmp) == 0:
                    pass
                else:
                    tmp.pop(-1)
            # print(f'i={i},j={j},tmp={tmp},output={output}')
        tmp_res = ''.join(i)
        if len(tmp) == 0 and tmp_res not in output:
            output.append(tmp_res)
    return output